﻿#include "util.h"
#include <iostream>
#include <algorithm>
#include <assert.h>

static bool randomInited = false;

static void initRandom()
{
	if (randomInited) return;

	srand((unsigned)time(nullptr));
	randomInited = true;
}

void generateSomeRandomNumbers(const int minValue, const int maxValue, int** numbers, const size_t size, const bool sorted)
{
	initRandom();
	int* rdNumbers = (int*)malloc(sizeof(int) * size);
	memset(rdNumbers, 0, sizeof(int) * size);

	int num;
	for (int i = 0; i < size; i++)
	{
		num = (rand() % (maxValue - minValue)) + minValue;
		*(rdNumbers + i) = num;
	}

	if (sorted)
	{
		sort(rdNumbers, rdNumbers + size, less<int>());
	}

	*numbers = rdNumbers;
}

int binarySearchTarget(const int* sortedNumbers, const size_t size, const int fromIndex, const int toIndex, const int target)
{
	if (!sortedNumbers || size == 0) return -1;
	if (sortedNumbers[fromIndex] == target) return fromIndex;
	if (sortedNumbers[toIndex] == target) return toIndex;
	if (fromIndex > toIndex) return -1;

	if (fromIndex == toIndex) return -1;

	int middleIndex = fromIndex + (toIndex - fromIndex) / 2;
	if (sortedNumbers[middleIndex] == target) return middleIndex;

	int leftIndex = binarySearchTarget(sortedNumbers, size, fromIndex, middleIndex - 1, target);
	if (leftIndex != -1) return leftIndex;

	int rightIndex = binarySearchTarget(sortedNumbers, size, middleIndex + 1, toIndex, target);
	return rightIndex;
}

int binarySearchNearestLessOrEqualThanTarget(const int* sortedNumbers, const size_t size, const int fromIndex, const int toIndex, const int target)
{
	if (!sortedNumbers || size == 0) return -1;
	if (fromIndex > toIndex) return -1;
	if (sortedNumbers[fromIndex] == target) return fromIndex;
	if (sortedNumbers[toIndex] == target) return toIndex;
	if (sortedNumbers[fromIndex] > target)return -1;
	if (sortedNumbers[toIndex] < target)return toIndex;
	if (fromIndex == toIndex) return -1;

	int middleIndex = fromIndex + (toIndex - fromIndex) / 2;
	if (sortedNumbers[middleIndex] == target) return middleIndex;

	if (middleIndex > fromIndex && sortedNumbers[middleIndex] > target && sortedNumbers[middleIndex - 1] < target) return middleIndex - 1;

	if (middleIndex + 1 <= toIndex && sortedNumbers[middleIndex + 1] > target && sortedNumbers[middleIndex] < target)return middleIndex;

	int leftIndex = binarySearchNearestLessOrEqualThanTarget(sortedNumbers, size, fromIndex, middleIndex - 1, target);

	int rightIndex = binarySearchNearestLessOrEqualThanTarget(sortedNumbers, size, middleIndex + 1, toIndex, target);

	if (leftIndex == -1) return rightIndex;
	if (rightIndex == -1)return leftIndex;

	if (abs(target - sortedNumbers[leftIndex]) > abs(target - sortedNumbers[rightIndex])) return rightIndex;

	return leftIndex;
}

int binarySearchNearestMoreOrEqualThanTarget(const int* sortedNumbers, const size_t size, const int fromIndex, const int toIndex, const int target)
{
	if (!sortedNumbers || size == 0) return -1;
	if (fromIndex > toIndex) return -1;
	if (sortedNumbers[fromIndex] == target) return fromIndex;
	if (sortedNumbers[toIndex] == target) return toIndex;
	if (sortedNumbers[fromIndex] > target) return fromIndex;
	if (sortedNumbers[toIndex] < target) return -1;
	if (fromIndex == toIndex) return -1;

	int middleIndex = fromIndex + (toIndex - fromIndex) / 2;
	if (sortedNumbers[middleIndex] == target) return middleIndex;

	if (middleIndex > fromIndex && sortedNumbers[middleIndex] > target && sortedNumbers[middleIndex - 1] < target) return middleIndex;

	if (middleIndex + 1 <= toIndex && sortedNumbers[middleIndex + 1] > target && sortedNumbers[middleIndex] < target) return middleIndex + 1;

	int leftIndex = binarySearchNearestMoreOrEqualThanTarget(sortedNumbers, size, fromIndex, middleIndex - 1, target);

	int rightIndex = binarySearchNearestMoreOrEqualThanTarget(sortedNumbers, size, middleIndex + 1, toIndex, target);

	if (leftIndex == -1) return rightIndex;
	if (rightIndex == -1)return leftIndex;

	if (abs(target - sortedNumbers[leftIndex]) > abs(target - sortedNumbers[rightIndex])) return rightIndex;

	return leftIndex;
}

static void swapCharacters(char* str, int index1, int index2)
{
	if (index1 == index2) return;

	str[index1] = str[index1] ^ str[index2];
	str[index2] = str[index1] ^ str[index2];
	str[index1] = str[index1] ^ str[index2];
}

static void getFullPermutationOfCharactersProcess(char* str, const size_t strSize, const int index, unordered_set<string>& strSet)
{
	if (index == strSize)
	{
		strSet.insert(str);
		return;
	}

	for (int i = index; i < strSize; i++)
	{
		swapCharacters(str, i, index);
		getFullPermutationOfCharactersProcess(str, strSize, index + 1, strSet);
		swapCharacters(str, i, index);
	}
}

void getFullPermutationOfCharacters(const char* str, unordered_set<string>& strSet)
{
	auto strSize = strlen(str);
	assert(strSize < 1000);

	char copyStr[1000] = { 0 };
	memcpy_s(copyStr, strSize, str, strSize);
	getFullPermutationOfCharactersProcess(copyStr, strSize, 0, strSet);
}

int main_util()
{
	int nums[] = { 2,4,6,8,10,12 };
	int size = sizeof(nums) / sizeof(int);
	int index = binarySearchNearestMoreOrEqualThanTarget(nums, size, 0, size - 1, 99);
	printf("nums[%d]=%d\n", index, nums[index]);

	return 0;
}